package algorithms;

import java.rmi.server.ObjID;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import com.sun.javafx.collections.MappingChange.Map;

public class Combination {
	int N = 0;
	public long ordinalOp = 0;
	public long dictOp = 0;
	public long transOp = 0;
	
	public Combination() {
		
	}
	public Combination(int N) {
		this.N = N;
	}
	
	public void setN(int n) {
		this.N = n;
	}

//序数法
	public int fac(int i){	//factorial阶乘
		if(i < 0){
			System.out.println("请输入一个大于等于0的整数！");
			return -1;
		} else if(i == 0 || i == 1){
			return 1;
		} else {
			return i*fac(i-1);
		}
	}
	
	public int[] toFacNum(int num) {	//转换成阶乘进制
		int[] a = new int[N];
		for(int i = 0;i<N;i++){
			a[i] = 0;
		}
		int fi = 1,fj = 2;
		while (num != 0) {
			ordinalOp++;
			int e = num%fj;
			num = num/fj;
			a[fi] = e;
			fi++;
			fj++;
		}
		return a;
	}
	
	public int[] FactoPermutation(int[] facNum) {	//阶乘进制转换为排列
		int[] arr = new int[N];
		int[] pointer = new int[N];
		for(int i = 0;i < N;i++){
			arr[i] = 0;
			pointer[i] = i;
		}
		
		for(int i = facNum.length - 1;i >= 0;i--){
			int p = facNum[i];
			int index = pointer[p];
			arr[index] = i + 1;
			while(p < N - 1){
				ordinalOp++;
				pointer[p] = pointer[p+1];
				p++;
			}
		}
		return arr;
	}
	
	public void ordinalOrder(){	//result
		for(int i = 0;i < fac(N);i++){
			int[] arr = FactoPermutation(toFacNum(i));
			for(int j = N-1;j >= 0;j--){
				System.out.print(arr[j] + " ");
			}
			
			System.out.println("");
		}
	}
	
	public long ordinalTime() {
		ordinalOp = 0;
		long beginTime = System.nanoTime();
		for(int i = 0;i < fac(N);i++){
			FactoPermutation(toFacNum(i));
		}
		long endTime = System.nanoTime();
		return endTime - beginTime;
	}

//字典序法
	public int[] nextDictOrder(int[] arr) {
		int m = 0,n = 0;
		for(int i = 1;i < arr.length;i++){
			if(arr[i-1] < arr[i]){
				dictOp++;
				m = i;
			}
		}
		
		for(int i = m;i < arr.length;i++){
			if(arr[m - 1] < arr[i]){
				dictOp++;
				n = i;
			}
		}
		
		int tmp = arr[m-1];
		arr[m-1] = arr[n];
		arr[n] = tmp;
		
		int len = arr.length-1;
		for(int i = m;i < (m+arr.length)/2;){
			dictOp++;
			tmp = arr[i];
			arr[i] = arr[len];
			arr[len] = tmp;
			i++;
			len--;
		}
		return arr;
	}
	public void dictOrder() {
		int[]	arr = new int[N];
		for(int i = 0;i < N;i++){
			arr[i] = i+1;
		}
		
		for(int i = 0;i < N;i++){	//初始序列
			System.out.print(arr[i]);
		}
		System.out.println("");
		
		for(int i = 1;i < fac(N);i++){
			arr = nextDictOrder(arr);
			for(int j = 0;j < arr.length;j++){
				System.out.print(arr[j]);
			}
			System.out.println("");
		}
		
	}
	
	
	public long dictTime() {
		dictOp = 0;
		int[]	arr = new int[N];
		for(int i = 0;i < N;i++){
			arr[i] = i+1;
		}
		long beginTime = System.nanoTime();
		for(int i = 1;i < fac(N);i++){
			arr = nextDictOrder(arr);
		}
		long endTime = System.nanoTime();
		return endTime-beginTime;
	}
	
//换位法
	class TranStruct {
		int[] arr;
		int[] stat;
		public TranStruct() {
			arr = new int[N];
			stat = new int[N];
		}
	}
	public TranStruct nextTransOrder(TranStruct ts) {
		int maxIndex = 0,maxNum = 0;
		
		for(int i = 0;i<ts.stat.length;i++){
			if(ts.stat[i] == -1){	//-1表示箭头向左
				if(i != 0){
					if(ts.arr[i] > ts.arr[i-1]){	//该数大于箭头所指方向的数字，则是活动状态
						if(ts.arr[i] > maxNum){	//该数是最大活动数
							maxNum = ts.arr[i];
							maxIndex = i;
							transOp++;
						}
					}
				}
			}
			if(ts.stat[i] == 1){	//1表示箭头向右
				if(i != ts.stat.length-1){
					if(ts.arr[i] > ts.arr[i+1]){	//该数处于活动状态
						if(ts.arr[i] > maxNum){	//该数是最大活动数
							maxNum = ts.arr[i];
							maxIndex = i;
							transOp++;
						}
					}
				}
			}
			
		}
		
		if(maxNum != 0){
			if(ts.stat[maxIndex] == -1){
				int tmp = ts.arr[maxIndex];
				ts.arr[maxIndex] = ts.arr[maxIndex-1];
				ts.arr[maxIndex-1] = tmp;
				
				int statTmp = ts.stat[maxIndex];
				ts.stat[maxIndex] = ts.stat[maxIndex-1];
				ts.stat[maxIndex-1] = statTmp;	
			}else if(ts.stat[maxIndex] == 1){
				int tmp = ts.arr[maxIndex];
				ts.arr[maxIndex] = ts.arr[maxIndex+1];
				ts.arr[maxIndex+1] = tmp;
				
				int statTmp = ts.stat[maxIndex];
				ts.stat[maxIndex] = ts.stat[maxIndex+1];
				ts.stat[maxIndex+1] = statTmp;
			}
			for(int i = 0;i < ts.arr.length;i++){
				if(ts.arr[i] > maxNum){
					ts.stat[i] = -ts.stat[i];	//所有比最大活动数大的数改变方向
					transOp++;
				}
			}
		}
		
		return ts;
	}
	
	public void transOrder(){
		TranStruct tranStruct = new TranStruct();
		for(int i = 0;i < N;i++){
			tranStruct.arr[i] = i+1;
			tranStruct.stat[i] = -1;
		}
		
		for(int i = 0;i < N;i++){	//初始序列
			System.out.print(tranStruct.arr[i]);
		}
		System.out.println("");
		
		for(int i = 1;i < fac(N);i++){
			tranStruct = nextTransOrder(tranStruct);
			for(int j = 0;j < N;j++){
				System.out.print(tranStruct.arr[j]);
			}
			System.out.println("");
		}
	}
	
	public long transTime() {
		transOp = 0;
		TranStruct tranStruct = new TranStruct();
		for(int i = 0;i < N;i++){
			tranStruct.arr[i] = i+1;
			tranStruct.stat[i] = -1;
		}
		long beginTime = System.nanoTime();
		for(int i = 1;i < fac(N);i++){
			tranStruct = nextTransOrder(tranStruct);
		}
		long endTime = System.nanoTime();
		return endTime-beginTime;
	}
	
	public static long avrList(List<String> list) {
		long total = 0;
		for (int i = 0; i < list.size(); i++) {
			total += Long.parseLong(list.get(i));
		}
		return total/list.size();
	}
	
	public static long avrTime(List<String> list) {
		long value;
		if (list.size() >= 20) {
			long avr = avrList(list);
			for (int i = 0; i < list.size(); i++) {
				value = Long.parseLong(list.get(i));
				if (value > 2*avr || value < avr/2) {
					list.remove(i);
				}
			}		
		}
		return avrList(list);
	}
	
	public int getTotal(int[] arr) {
		int total = 0;
		for(int i=0;i<arr.length;i++){
			if (arr[i] == 1) {
				total++;
			}
		}
		return total;
	}
	
	public void test(Object object) {
		System.out.println(object);
	}
	
	public int[] isOne(int[] arr) {
		int total = getTotal(arr);
		int sum=0;
		int index = arr.length-1;
		while (index>=0) {
			if (arr[index] == 1) {
				sum++;
				
				if (sum == total) {
					return null;
				}
			}else {
				for(int i = index;i>=0;i--){
					if (arr[i] == 1) {
						arr[i] = 0;
						i++;
						for(int j = 0;i<arr.length;j++,i++){
							if (j <= sum) {
								arr[i] = 1;
							}else {
								arr[i] = 0;
							}
						}
						return arr;
					}
				}
			}
			index--;
		}
		return null;
	}
	
	public int[] isZero(int[] arr) {
		int index = arr.length-1;
		while (index>=0) {
			if (arr[index] == 1) {
				arr[index] = 0;
				arr[index+1] =1;
				return arr;
			}
			index--;
		}
		return null;
	}
	
	public int[] nextCombination(int[] arr) {
		int[] result = null;
		int i = arr.length-1;
		if (arr[i] == 0) {
			result = isZero(arr);
		}else {
			result = isOne(arr);
		}
		return result;
	}
	
	public int[] getArrayByFlag(int[] data,int[] flag, int len) {
		int[] arr = new int[len];
		for(int i=0,j=0;i<flag.length;i++){
			if (flag[i] == 1) {
				arr[j] = data[i];
				j++;
			}
		}
		return arr;
	}
	
	public int compare(int[] arr,char[] pwd) {
		int ret = -1;
		for(int i = 0;i < pwd.length;i++){
			if (arr[i]+48 == pwd[i]) {
				ret = 1;
			}else{
				ret = -1;
				break;
			}
		}
		return ret;
	}
	
	public int[] getArrange(int[] arr,int[] pointer) {
		if (arr.length != pointer.length) {
			return null;
		}
		int len = arr.length;
		int[] ret = new int[len];
		for(int i = 0;i< len;i++){
			ret[i] = arr[pointer[i]-1];
		}
		return ret;
	}
	
	public int decode(String val) {
		int ret = -1,len = val.length();
		
		int[] arr = new int[len];
		int[] arrangedArr = new int[len];
		
		char[] pwd = val.toCharArray();
		int[] data = {0,1,2,3,4,5,6,7,8,9};
		int[] flag = new int[data.length];
		int[] pointer = new int[len];
		
		for (int i = 0; i < data.length; i++) {
			if (i < len) {
				flag[i] = 1;
			}else{
				flag[i] = 0;
			}
		}
		
		while (flag != null) {
			for(int i = 0;i < len;i++){
				pointer[i] = i+1;
			}
			arr = getArrayByFlag(data, flag, len);

			for(int i = 1;i < fac(len);i++){
				arrangedArr = getArrange(arr, pointer);
				ret = compare(arrangedArr, pwd);
				if (ret == 1) {
					return ret;
				}
				
				pointer = nextDictOrder(pointer);
			}
			
			flag = nextCombination(flag);
		}
		
		return ret;
	}
	
	
}
